1. Field of the Invention
The invention relates to a candidate list augmentation apparatus and method for channel coding system, and more particularly, a candidate list augmentation apparatus which is able to detect signal with dynamic compensation in the multi-input multi-output (MIMO) channel coding systems.
2. Description of the Related Art
Multiple input multiple output (MIMO) technology draws great attention due to its ability to improve transmission efficiency. Among several MIMO detection schemes, maximum likelihood (ML) detection is one of the most well known in the art which is being commonly used to fully utilize the diversity gain. With an additive white Gaussian channel noise assumption, ML detection can be reduced to a closest-point-search problem in a given lattice. Moreover, although MIMO system performance is boosted by the diversity gain, channel coding is often employed to provide extra coding gain such that systems are allowed to perform better in case of lower signal-to-noise-ratio (SNR). Since exhaustive search is infeasible for large number of antennas or high level signal modulation, sphere decoding has been proposed to perform exhaustive search after confining the search range by a radius. With properly chosen radius, sphere decoding has been proved to approach the performance of ML detection.
Please refer to FIG. 1 for a block diagram schematically showing a conventional MIMO system 100 with channel coding schemes. The conventional MIMO system 100 includes a channel encoder 102, a spatial mapping device 104, a transmit device 106, a receive device 108, a sphere decoder 110, and a channel decoder 112. Assume that the transmit device 106 includes Nt transmit antennas and the receive device 108 includes Nr antennas. The channel encoder 102 is utilized to channel code the original signal u and generate the coded bits x=[x(1), x(2), . . . , x(L)]T. The spatial mapping device 104 then modulates the coded bits x through L time slots. Here, Each vector x(t)=[x1(t), x2(t), . . . , xNt×2Mc(t)] with the time index t is mapped to the transmitted vector {tilde over (s)}(1)=[{tilde over (s)}1(t),{tilde over (s)}2(t) . . . {tilde over (s)}Nt(t)]T by {tilde over (M)}(•), which maps 2Mc bits to a complex signal. For simplicity, the spatial mapping in the spatial mapping device 104 refers to direct spatial multiplexing, and M2-QAM-mapped signals are considered henceforth.
After mapping the signal, the transmit device 106 transmits through the complex signal based on the transmitted vector {tilde over (s)}(t) and the receive device 108 receives the real signal according to the received vector {tilde over (y)}(t). The relation between the transmitted vector {tilde over (s)}(t) and the received vector {tilde over (y)}(t) can be expressed by:{tilde over (y)}(t)={tilde over (H)}(t){tilde over (s)}(t)+ñ(t)  (1)where the channel {tilde over (H)}(t) is an Nr×Nt matrix of independent and identically distributed (i.i.d.) complex Gaussian random variables; ñ(t) is an Nr×1 i.i.d. complex Gaussian noise vector. The complex model in the equation (1) can be further rewritten as:
                              y                      (            t            )                          =                              [                                                                                R                    ⁢                                          {                                                                        y                          ~                                                                          (                          t                          )                                                                    }                                                                                                                                        L                    ⁢                                          {                                                                        y                          ~                                                                          (                          t                          )                                                                    }                                                                                            ]                    =                                                                      [                                                                                                                                          R                            ⁢                                                          {                                                                                                y                                  ~                                                                                                  (                                  t                                  )                                                                                            }                                                                                ,                                                                                                                                                  -                            L                                                    ⁢                                                      {                                                                                          H                                ~                                                                                            (                                t                                )                                                                                      }                                                                                                                                                                                                                    L                            ⁢                                                          {                                                                                                H                                  ~                                                                                                  (                                  t                                  )                                                                                            }                                                                                ,                                                                                                                      R                          ⁢                                                      {                                                                                          y                                ~                                                                                            (                                t                                )                                                                                      }                                                                                                                                ]                                ⁡                                  [                                                                                                              R                          ⁢                                                      {                                                                                          s                                ~                                                                                            (                                t                                )                                                                                      }                                                                                                                                                                                        L                          ⁢                                                      {                                                                                          s                                ~                                                                                            (                                t                                )                                                                                      }                                                                                                                                ]                                            +                              [                                                                                                    R                        ⁢                                                  {                                                                                    n                              ~                                                                                      (                              t                              )                                                                                }                                                                                                                                                                        L                        ⁢                                                  {                                                                                    n                              ~                                                                                      (                              t                              )                                                                                }                                                                                                                    ]                                      =                                                            H                                      (                    t                    )                                                  ⁢                                  s                                      (                    t                    )                                                              +                              n                                  (                  t                  )                                                                                        (        2        )            where R{•} and L{•} refer to the real and the imaginary parts, respectively, of the complex signal s(t). Thus, the Nt-dimensional complex M2-QAM signals s(t) are transformed into 2Nt-dimensional real M-PAM signals y(t). For simpler notation, the time index t will be omitted hereafter.
Based on the equation (2), ML solution can be derived by searching all over the 2Nt-dimensional constellation space Ω2Nt for the minimizer:
                                          s            ^                    ML                =                              arg                    ⁢                                    max                                                s                  ′                                ∈                                  Ω                                      2                    ⁢                                          N                      t                                                                                            ⁢                                                                            y                  -                                      Hs                    ′                                                                              2                                                          (        3        )            where the cost function ∥•∥2 refers to Euclidean norm. As shown in the equation (3), the exhaustive search for the minimizer ŝML becomes infeasible since the computation grows exponentially with Nt and L. Therefore, the sphere decoder 110 in the conventional MIMO system utilizes sphere decoding algorithm as a means to solve the closest-lattice-point searching problem.
The sphere decoder 110 first confines the search range by a predefined radius r; and only the path metric of the s′ in the hypersphere ∥y−Hs′∥2≦r2 will be compared. That is, the equation (2) can be computed by:
                                                        s              ^                        ML                    ≈                                    s              ^                        SD                          =                              arg                    ⁢                                    min                                                                    s                    ′                                    ∈                                      Ω                                          2                      ⁢                                              N                        t                                                                                            ,                                                                                                                          y                        -                                                  Hs                          ′                                                                                                            2                                    ≤                                      r                    2                                                                        ⁢                                                                            y                  -                                      Hs                    ′                                                                              2                                                          (        4        )            
Here, if the radius r is chosen properly such that at least one path s′ satisfies the radius constraint.
Next, the sphere decoder 110 will preprocess on y to transform the equation (4) into a tree-search problem. By QR-decomposition, for instance, the channel matrix is decomposed by H=QR where QTQ=I2Nr, an identity matrix of size 2Nr, and R is a 2Nt×2Nt upper triangular matrix. By multiplying y with QT, the sphere decoder 110 can transformed the equation (4) into:
                                          s            ^                    ML                =                              arg                    ⁢                                    min                                                s                  ′                                ∈                                  Ω                                      2                    ⁢                                          N                      t                                                                                            ⁢                                                                            q                  -                                      Rs                    ′                                                                              2                                                          (        5        )            where q=[q1, q2, . . . , q2Nt]=QTy. Each s′ in Ω2Nt is defined as a “path” that traverses from the root to the leaf of the search tree. Every path consists of 2Nt nodes representing the 2Nt points of the 2Nt-layered tree. Moreover, the cost function of each path, i.e. ∥q−Rs′∥2, will be referred to “path metric” and can be calculated by:
                                                                    q              -                              Rs                ′                                                          2                =                                            ∑                              i                =                1                                            2                ⁢                Nt                                      ⁢                                          (                                                      q                    i                                    -                                                            ∑                                              j                        =                        i                                                                    2                        ⁢                        Nt                                                              ⁢                                                                  R                                                  i                          ,                          j                                                                    ⁢                                              s                        j                                                                                            )                            2                                =                                    ∑                              i                =                1                                            2                ⁢                Nt                                      ⁢                          e              ⁡                              (                                  s                                      (                    i                    )                                                  )                                                                        (        6        )            where s(i) represents the i-th to 2Nt-th elements of s′, that is, s(i)=[si, si+1, . . . , s2Nt]T. Moreover, the partial Euclidean distance (PED) of s(i), T(s(i)), is defined by:
                              T          ⁡                      (                          s                              (                i                )                                      )                          =                                            ∑                              i                =                1                                            2                ⁢                Nt                                      ⁢                                          (                                                      q                                          i                      ′                                                        -                                                            ∑                                              j                        =                                                  i                          ′                                                                                            2                        ⁢                        Nt                                                              ⁢                                                                  R                                                                              i                            ′                                                    ,                          j                                                                    ⁢                                              s                        j                                                                                            )                            2                                =                                    T              ⁡                              (                                  s                                      (                                          i                      +                      1                                        )                                                  )                                      +                          e              ⁡                              (                                  s                                      (                    i                    )                                                  )                                                                        (        7        )            
Based on this conventional sphere decoding algorithm, the minimizer ŝML can be found as long as each path has been searched. However, the traditional sphere decoding algorithm remains a major challenge in acquiring accurate probabilistic information. Limited by the complex computation of sphere decoding, and inconstant decoding throughput could cause inefficient VLSI implementation.
Different from the sphere decoding algorithm that outputs only the ML path, the conventional MIMO system utilizes the modified list sphere decoding algorithm to deliver a candidate list L that consists of the most reliable paths. Please refer to FIG. 2 for a block diagram schematically showing another conventional MIMO system 200 with list sphere coding schemes. The conventional MIMO system 200 includes a channel encoder 202, a spatial mapping device 204, a transmit device 206, a receive device 208, a list sphere decoder 210, and a channel decoder 216. Since the elements of the same name in the FIG. 1 and FIG. 2 have the same function and operation, detailed description is omitted for the sake of brevity. The main different between the MIMO systems 100 and 200 is that the MIMO systems 200 further includes the list sphere decoder 210. The list sphere decoder 210 includes a candidate list generation device 212 and a soft value generation device 214. The candidate list generation device 212 is utilized to generate a candidate list L. Assume that |L| is the list size. Based on the system model in the equation (2), the most reliable |L| paths are equivalent to the paths corresponding to the least |L| path metrics. After generating the candidate list L, the soft value generation device 214 then computes the soft input signal from the list L for the subsequent channel decoder 216. Different soft input signal can result in different error correcting capability for the following channel decoding. The operation of the candidate list generation device 212 and the soft value generation device 214 are further detailed as follows.
Let M(•) denote the M-PAM mapping function such that sk=M(xk,1, xk,2, . . . , xk,Mc). For any path s′ε L, the soft value of xk,j is defined by its “a posteriori” probabilities:
                                                                        L                ⁡                                  (                                      x                                          k                      ,                      j                                                        )                                            =                              log                ⁢                                                      Pr                    ⁡                                          (                                                                        x                                                      k                            ,                            j                                                                          =                                                  0                          |                          y                                                                    )                                                                            Pr                    ⁡                                          (                                                                        x                                                      k                            ,                            j                                                                          =                                                  1                          |                          y                                                                    )                                                                                                                                              =                                                log                  ⁢                                                            Pr                      ⁡                                              (                                                                              x                                                          k                              ,                              j                                                                                =                          0                                                )                                                                                    Pr                      ⁡                                              (                                                                              x                                                          k                              ,                              j                                                                                =                          1                                                )                                                                                            +                                  log                  ⁢                                                            Pr                      ⁡                                              (                                                                              y                            |                                                          x                                                              k                                ,                                j                                                                                                              =                          0                                                )                                                                                    Pr                      ⁡                                              (                                                                              y                            |                                                          x                                                              k                                ,                                j                                                                                                              =                          1                                                )                                                                                                                                                                                        (              8              )                                                                                                                                                    (              9              )                                          The first term in the equation (9), which is the “a priori” information, is zero for the ML detection or can be computed by the extrinsic information provided by the channel decoder in an iterative detection decoding process. The second term in the equation (9) can be computed by:
                              log          ⁢                                    Pr              ⁡                              (                                                      y                    |                                          x                                              k                        ,                        j                                                                              =                  0                                )                                                    Pr              ⁡                              (                                                      y                    |                                          x                                              k                        ,                        j                                                                              =                  1                                )                                                    =                  log          ⁢                                                    ∑                                                      s                    ′                                    ∈                                      Ω                                          j                      ,                      0                                                                                  ⁢                              Pr                ⁡                                  (                                      y                    |                                          s                      ′                                                        )                                                                                    ∑                                                      s                    ′                                    ∈                                      Ω                                          j                      ,                      1                                                                                  ⁢                              Pr                ⁡                                  (                                      y                    |                                          s                      ′                                                        )                                                                                        (        10        )                                ≈                              1                          2              ⁢                              σ                2                                              ⁢                      (                                                            min                                                            s                      ′                                        ∈                                          Ω                                              j                        ,                        1                                                                                            ⁢                                                                                                y                      -                                              Hs                        ′                                                                                                  2                                            -                                                min                                                            s                      ′                                        ∈                                          Ω                                              j                        ,                        0                                                                                            ⁢                                                                                                y                      -                                              Hs                        ′                                                                                                  2                                                      )                                              (        11        )                                ≈                              1                          2              ⁢                              σ                2                                              ⁢                      (                                                            min                                                            s                      ′                                        ∈                                                                  Ω                                                  j                          ,                          1                                                                    ⋂                      L                                                                      ⁢                                                                                                y                      -                                              Hs                        ′                                                                                                  2                                            -                                                min                                                            s                      ′                                        ∈                                                                  Ω                                                  j                          ,                          0                                                                    ⋂                      L                                                                      ⁢                                                                                                y                      -                                              Hs                        ′                                                                                                  2                                                      )                                              (        12        )            Where σ2 is the noise variance, and Ωj,b is the set of all path s′ having xk,j=b for b=0, 1. That is, Ωj,0 represents the set of all s′ having xk,j=0, and Ωj,0 represents the set of all s′ having xk,j=1. Usually, the candidate list generation device 212 will generate a sufficiently large list to ensure a high probability in finding the true minimizer in the equation (11) with (12). With preprocessing, the equation (12) will be replaced by:
                              1                      2            ⁢                          σ              2                                      ⁢                  (                                                    min                                                      s                    ′                                    ∈                                                            Ω                                              j                        ,                        1                                                              ⋂                    L                                                              ⁢                                                                                      q                    -                                          Rs                      ′                                                                                        2                                      -                                          min                                                      s                    ′                                    ∈                                                            Ω                                              j                        ,                        0                                                              ⋂                    L                                                              ⁢                                                                                      q                    -                                          Rs                      ′                                                                                        2                                              )                                    (        13        )            
However, when one of the sets Ωj,0 and Ωj,0 can not find the path s′ in the list L (i.e. Ωj,0∩L=0 or Ωj,1∩L=0), it is impossible to find the minimizer in an empty set, and the minima is often approximated by a predefined large constant. Being the soft input signals to the subsequent channel decoder 216, the additional interference resulted from the approximation inaccuracy can degrade the error performance. Although the degradation can be mitigated by increasing the list size to reduce the probability of Ωj,0∩L (or Ωj,1∩L), being an empty set, the computation complexity in generating the candidate list also increases.
Therefore, to solve the above-mentioned problems, the present invention proposes a novel candidate list augmentation apparatus for channel coding system and method thereof along with dynamic compensation to improve the efficiency and performance of the coded MIMO systems.